/*---------------------------------------------------------------------------*\
  =========                 |
  \\      /  F ield         | cfMesh: A library for mesh generation
   \\    /   O peration     |
    \\  /    A nd           | Author: Franjo Juretic (franjo.juretic@c-fields.com)
     \\/     M anipulation  | Copyright (C) Creative Fields, Ltd.
-------------------------------------------------------------------------------
License
    This file is part of cfMesh.

    cfMesh is free software; you can redistribute it and/or modify it
    under the terms of the GNU General Public License as published by the
    Free Software Foundation; either version 3 of the License, or (at your
    option) any later version.

    cfMesh is distributed in the hope that it will be useful, but WITHOUT
    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
    FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
    for more details.

    You should have received a copy of the GNU General Public License
    along with cfMesh.  If not, see <http://www.gnu.org/licenses/>.

Class
    meshOctree

Description
    Octree for mesh generation

SourceFiles
    meshOctree.C

\*---------------------------------------------------------------------------*/

#ifndef meshOctree_H
#define meshOctree_H

#include "DynList.H"
#include "meshOctreeSlot.H"
#include "meshOctreeCube.H"
#include "patchRefinementList.H"
#include "Pair.H"

// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //

namespace Foam
{

// Forward declarations
class triSurf;

/*---------------------------------------------------------------------------*\
                           Class meshOctree Declaration
\*---------------------------------------------------------------------------*/

class meshOctree
{
    // Private data
        //- Reference to surface to work on
        const triSurf& surface_;

        //- neighbouring processors which can exchange data with the current one
        //- this is only used in case of parallel calculations
        labelList neiProcs_;

        //- this list contains the first the last octree box coordinates on
        //- a neighbour processor. They are used for parallel runs when the
        //- leaves are sorted in Morton's Z-order
        List<Pair<meshOctreeCubeCoordinates> > neiRange_;

        //- Root cube of the octree structure
        meshOctreeCube* initialCubePtr_;
        label initialCubeRotation_;
        boundBox rootBox_;
        bool isRootInitialised_;

        //- octree search range
        scalar searchRange_;

        //- vectors pointing into each octant
        //- they are useful during creation of vertex labels
        FixedList<Vector<label>, 8> octantVectors_;
        FixedList<FixedList<meshOctreeCubeCoordinates, 8>, 8> vrtLeavesPos_;
        FixedList<meshOctreeCubeCoordinates, 26> regularityPositions_;

        //- List of slots containing data generated by each processor
        List<meshOctreeSlot> dataSlots_;

        //- list of cubes which are leaves of the octree
        LongList<meshOctreeCube*> leaves_;

        //- a flag whether is true if is it a quadtree
        const bool isQuadtree_;

    // Private member functions
        //- set data needed for finding neighbours
        void setOctantVectorsAndPositions();

        //- create initial octree box
        void createInitialOctreeBox();

        //- return leaf cube for the given position
        meshOctreeCube* findCubeForPosition
        (
            const meshOctreeCubeCoordinates&
        ) const;

        //- find leaves contained in the box
        void findLeavesContainedInBox
        (
            const boundBox&,
            DynList<const meshOctreeCube*, 256>&
        ) const;

    // Private copy constructor
        //- Disallow default bitwise copy construct
        meshOctree(const meshOctree&);

        //- Disallow default bitwise assignment
        void operator=(const meshOctree&);

public:

    friend class meshOctreeModifier;

    // Constructors

        //- Construct from surface
        meshOctree(const triSurf&, const bool isQuadtree = false);

    // Destructor

        ~meshOctree();


    // Member Functions

        //- find a cube containing the vertex
        label findLeafContainingVertex(const point&) const;

        //- find leaves within the given range from the given point
        void findLeavesInSphere
        (
            const point&,
            const scalar,
            DynList<label>&
        ) const;

        //- is octree a quadtree or an octree
        inline bool isQuadtree() const;

        //- return octant vectors
        inline const FixedList<Vector<label>, 8>& octantVectors() const;

        //- return leaves of the octree
        inline label numberOfLeaves() const;
        inline const meshOctreeCubeBasic& returnLeaf(const label) const;
        inline short leafAtProc(const label) const;
        void findBoundaryPatchesForLeaf(const label, DynList<label>&) const;
        inline bool hasContainedTriangles(const label) const;
        inline void containedTriangles(const label, DynList<label>&) const;
        inline bool hasContainedEdges(const label) const;
        inline void containedEdges(const label, DynList<label>&) const;


        //- checks if the point is inside or outside the surface
        bool isPointInside(const point&) const;

        //- find nearest surface point for vertex and its region
        void findNearestSurfacePoint
        (
            point& nearest,
            scalar& distSq,
            label& nearestTriangle,
            label& region,
            const point& p
        ) const;

        //- find nearest surface point for vertex in a given region
        void findNearestSurfacePointInRegion
        (
            point& nearest,
            scalar& distSq,
            label& nearestTriangle,
            const label region,
            const point& p
        ) const;

        //- find nearest feature-edges vertex to a given vertex
        bool findNearestEdgePoint
        (
            point& edgePoint,
            scalar& distSq,
            label& nearestEdge,
            const point& p,
            const DynList<label>& regions
        ) const;

        bool findNearestPointToEdge
        (
            point& nearest,
            scalar& distSq,
            label& nearestEdge,
            const FixedList<point, 2>& edgePoints,
            const FixedList<label, 2>& edgePointRegions
        ) const;

        //- find nearest corner point
        bool findNearestCorner
        (
            point& nearest,
            scalar& distSq,
            label& nearestPoint,
            const point& p,
            const DynList<label>& patches
        ) const;

        //- find the nearest vertex to the given patches
        bool findNearestPointToPatches
        (
            point& nearest,
            scalar& distSq,
            const point& p,
            const DynList<label>& patches,
            const scalar tol = 1e-4
        ) const;

        //- return a reference to the surface
        inline const triSurf& surface() const;

        //- find a neighbour over a cube's node
        label findNeighbourOverNode
        (
            const meshOctreeCubeCoordinates&,
            const label nodeI
        ) const;

        //- find neighbours over a cube's edge
        void findNeighboursOverEdge
        (
            const meshOctreeCubeCoordinates&,
            const label eI,
            DynList<label>& neighbourLeaves
        ) const;

        //- find neighbours over a leaf cube face in the given direction
        void findNeighboursInDirection
        (
            const meshOctreeCubeCoordinates&,
            const label dir,
            DynList<label>& neighbourLeaves
        ) const;

        //- find neighbour leaf cubes over all faces
        void findNeighboursForLeaf
        (
            const meshOctreeCubeCoordinates&,
            DynList<label>& neighbourLeaves
        ) const;

        //- find neighbour leaves over nodes, edges and faces
        void findAllLeafNeighbours
        (
            const meshOctreeCubeCoordinates&,
            DynList<label>& neighbourLeaves
        ) const;

        //- find neighbours over a cube's node
        inline label findNeighbourOverNode
        (
            const label leafI,
            const label nodeI
        ) const;

        //- find neighbours over a cube's edge
        inline void findNeighboursOverEdge
        (
            const label leafI,
            const label eI,
            DynList<label>& neighbourLeaves
        ) const;

        //- find neighbouring leaves of a leaf cube
        inline void findNeighboursInDirection
        (
            const label leafI,
            const label dir,
            DynList<label>&
        ) const;

        //- find neighbours over faces
        inline void findNeighboursForLeaf
        (
            const label,
            DynList<label>&
        ) const;

        //- find neighbours over nodes, edges and faces
        inline void findAllLeafNeighbours
        (
            const label,
            DynList<label>&
        ) const;

        //- return leaf cube for the given position
        label findLeafLabelForPosition
        (
            const meshOctreeCubeCoordinates&
        ) const;

        //- find neighbouring leaves of a vertex
        void findLeavesForCubeVertex
        (
            const label,
            const direction,
            FixedList<label, 8>&
        ) const;

        //- find all leaves contained within the given boundBox
        void findLeavesContainedInBox(const boundBox&, labelList&) const;
        void findLeavesContainedInBox(const boundBox&, DynList<label>&) const;

        void findEdgesInBox(const boundBox&, DynList<label>&) const;
        void findTrianglesInBox(const boundBox&, DynList<label>&) const;

        //- return rootBox
        inline const boundBox& rootBox() const;

        //- return positions which need to be searched
        //- to achieve 1-irregular octree
        inline const FixedList<meshOctreeCubeCoordinates, 26>&
        regularityPositions() const;

        //- return positions to find the leaves at each cube node
        inline const FixedList<FixedList<meshOctreeCubeCoordinates, 8>, 8>&
        positionsOfLeavesAtNodes() const;

        //- exchange requests with other processors generating the octree
        void exchangeRequestsWithNeighbourProcessors
        (
            const LongList<meshOctreeCubeCoordinates>& dataToSend,
            LongList<meshOctreeCubeCoordinates>& dataToReceive
        ) const;

        //- exchange requests with other processors generating the octree
        void exchangeRequestsWithNeighbourProcessors
        (
            const LongList<meshOctreeCubeCoordinates>& dataToSend,
            const LongList<scalar>& rangesToSend,
            LongList<meshOctreeCubeCoordinates>& dataToReceive,
            LongList<scalar>& receivedRanges
        ) const;

        //- neighbour processors of the current one
        inline const labelList& neiProcs() const;
};


// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //

} // End namespace Foam

// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //

#include "meshOctreeI.H"

// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //

#endif

// ************************************************************************* //
